home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Sample Code / Newton Sample Code 1.2 / Data Storage (Soups) / LostInSpaceCode / SearchUtils.f < prev   
Encoding:
Text File  |  1994-03-19  |  3.8 KB  |  131 lines  |  [TEXT/R*ch]
  1. /*
  2. ** Copyright: © Michael S. Engber, 1994. All Rights Reserved.
  3. **
  4. ** SearchUtils.f
  5. **
  6. ** Binary search routines
  7. **
  8. */
  9.  
  10. //DataUtils.f must be loaded first
  11. // (defines some constants)
  12.  
  13. //
  14. // utils for searching array of frames rep
  15. //
  16.  
  17. func BSearchArrayOfFrames(array,key)
  18. begin
  19.   local lPos := 0;
  20.   local rPos := Length(array) - 1;
  21.   local mPos;
  22.     
  23.   while lPos <= rPos do
  24.       begin
  25.         mPos := (lPos + rPos) DIV 2;
  26.         mVal := array[mPos].slot2;
  27.         if mVal > key then
  28.           rPos := mPos - 1;
  29.         else
  30.           lPos := mPos + 1;
  31.       end;
  32.     
  33.     if rPos>=0 AND StrEqual(array[rPos].slot2,key) then rPos;
  34. end;
  35.  
  36. /*
  37. // test code
  38. testData := [{slot2: "b"},{slot2: "d"},{slot2: "f"}];
  39. if BSearchArrayOfFrames(testData,"a") <> nil then Print("*error*");
  40. if BSearchArrayOfFrames(testData,"b") <> 0   then Print("*error*");
  41. if BSearchArrayOfFrames(testData,"c") <> nil then Print("*error*");
  42. if BSearchArrayOfFrames(testData,"d") <> 1   then Print("*error*");
  43. if BSearchArrayOfFrames(testData,"e") <> nil then Print("*error*");
  44. if BSearchArrayOfFrames(testData,"f") <> 2   then Print("*error*");
  45. if BSearchArrayOfFrames(testData,"g") <> nil then Print("*error*");
  46. */
  47.  
  48.  
  49. //
  50. // utils for searching array of arrays rep
  51. //
  52.  
  53. func BSearchArrayOfArrays(array,key)
  54. begin
  55.   local lPos := 0;
  56.   local rPos := Length(array) - 1;
  57.   local mPos;
  58.     
  59.   while lPos <= rPos do
  60.       begin
  61.         mPos := (lPos + rPos) DIV 2;
  62.         mVal := array[mPos][1];
  63.         if mVal > key then
  64.           rPos := mPos - 1;
  65.         else
  66.           lPos := mPos + 1;
  67.       end;
  68.     
  69.     if rPos>=0 AND StrEqual(array[rPos][1],key) then rPos;
  70. end;
  71.  
  72. /*
  73. // test code
  74. testData := [[nil,"b"],[nil,"d"],[nil,"f"]];
  75. if BSearchArrayOfArrays(testData,"a") <> nil then Print("*error*");
  76. if BSearchArrayOfArrays(testData,"b") <> 0   then Print("*error*");
  77. if BSearchArrayOfArrays(testData,"c") <> nil then Print("*error*");
  78. if BSearchArrayOfArrays(testData,"d") <> 1   then Print("*error*");
  79. if BSearchArrayOfArrays(testData,"e") <> nil then Print("*error*");
  80. if BSearchArrayOfArrays(testData,"f") <> 2   then Print("*error*");
  81. if BSearchArrayOfArrays(testData,"g") <> nil then Print("*error*");
  82.  */
  83.  
  84.  
  85. //
  86. // utils for searching binary object rep
  87. //
  88.  
  89. //from DataUtils.f - which must be loaded first
  90. //constant kSlot1Offset := 0;  //a long (4 bytes)
  91. //constant kSlot2Offset := 4;  //a cstring of (8 bytes = up to 7 chars + terminating null) 
  92. //constant kSlot3Offset := 12; //a word (2 bytes)
  93. //constant kSlot4Offset := 14; //a byte
  94. //constant kDatumSize   := 15;
  95.  
  96. func BSearchBinaryObj(binObj,key)
  97. begin
  98.   local lPos := 0;
  99.   local rPos := (Length(binObj) DIV kDatumSize) - 1;
  100.   local mPos;
  101.    
  102.   while lPos <= rPos do
  103.       begin
  104.         mPos := (lPos + rPos) DIV 2;
  105.         mVal := ExtractCString(binObj,mPos*kDatumSize + kSlot2Offset);
  106.         if mVal > key then
  107.           rPos := mPos - 1;
  108.         else
  109.           lPos := mPos + 1;
  110.       end;
  111.     
  112.     if rPos>=0 AND StrEqual(ExtractCString(binObj,rPos*kDatumSize + kSlot2Offset),key) then rPos*kDatumSize;
  113. end;
  114.  
  115. /*
  116. // test code
  117. testData := SetLength("\u000000006200000000000000000000000000006400000000000000000000000000006600000000000000000000",3*kDatumSize);
  118. if BSearchBinaryObj(testData,"a") <> nil            then Print("*error*");
  119. if BSearchBinaryObj(testData,"b") <> 0*kDatumSize   then Print("*error*");
  120. if BSearchBinaryObj(testData,"c") <> nil            then Print("*error*");
  121. if BSearchBinaryObj(testData,"d") <> 1*kDatumSize   then Print("*error*");
  122. if BSearchBinaryObj(testData,"e") <> nil            then Print("*error*");
  123. if BSearchBinaryObj(testData,"f") <> 2*kDatumSize   then Print("*error*");
  124. if BSearchBinaryObj(testData,"g") <> nil            then Print("*error*");
  125.  */
  126.  
  127. //define constants - we really want to use these fns at run time
  128. DefConst('kBSearchArrayOfFramesFn, functions.BSearchArrayOfFrames);
  129. DefConst('kBSearchArrayOfArraysFn, functions.BSearchArrayOfArrays);
  130. DefConst('kBSearchBinaryObjFn,     functions.BSearchBinaryObj);
  131.